APPENDIX	ISIS


Introduction

	In this appendix, we describe the operation of ISIS 
(Interactive Scene Interpretation System).  ISIS allows a user 
to define regions by indicating points in the region, or vertex 
points on the boundary.  The system can compute various attributes 
(such as hue or height) of either regions or samples.

	ISIS is an integrated set of INTERLISP functions facilitating
the development and testing of pictorial representations. The LISP
functions communicate with FORTRAN subprograms residing in an
inferior fork. The system consists of an image file, a 
library of primitive feature extraction functions, a means for 
applying selected primitive operators to graphically designated areas
of a scene, and an iconic data structure for retaining pictorial
examples.

Iconic regions are represented as an explicit list of picture
samples and/or as a list of vertices describing a closed
polygonal boundary.  A bounding rectangle is also
determinable for each region.  Efficient routines exist for
determining whether a given picture element is contained within
a bounded region, for obtaining a set of samples over a bounded
region, and for fitting a boundary around a set of samples.

Images are stored in a 120 x 120 array, each picture cell
characterized by tv brightness through red, green, blue, and neutral
filters and by a range measurement (the range measurements are
output of a time-of-flight range finder, or simulated output of this 
device which is still undergoing improvement).  High resolution
vector displays and an MOS-refreshed color video monitor with a
low resolution vector overlay serve as graphic output devices.
Both displays allow the user to select points on the screen with
a cursor.



Definitions

	We begin the discussion of the system by defining some basic
data representations and concepts.



	<sample>	a point in the image. A sample is represented
		by the dotted pair of its I and J (i.e. horizontal 
		and vertical) components, i.e. (I . J).

	<samplelist>	a list of samples of the form:
		(SAMPLE <sample> ... <sample>).

	<boundary>	a list of samples of the form:
		(<sample> <sample> ... <sample>),
		where the first and last samples in the list are EQUAL.
		The samples form the vertices of a closed polygon.

	<region>	a <sample region> or a <boundary region>.
		Efficient functions exist to convert between the two. 

	<sample region>	a region composed of the set of samples in
		an associated samplelist.

	<boundary region>	a region consisting of the area delimited
		by the polygon represented by an associated boundary
		list.

	<region number>	the canonical representation for a region.
		The region number is a unique integer between
		1 and the value of the global, RCT (the maximum number 
		of regions created up to that point). 

	<alias>		a non-unique atomic name for a region.
		An alias may be associated with at most one
		region, but a region may have several aliases.


	<current region>	initially region number 1,
		the entire picture. The current region is the most
		recent region created by NEWREGION (see below).

	<region designator> is one of the following:

		<region number>
		<alias>
		<sample list> - either refers to an existing region with an EQ 
			samplelist, or a new sample region
			is created.
		<boundary list> - either refers to an existing region with an
			EQ boundary list, or a new boundary region
			is created.
		MOUSE or M - allows the user to select a list of sample
			  points with the mouse (the display cursor), choosing
			  points with the left button, verifying
			  with the middle button, and terminating
			  the selections with the right button.
			  If a single point is selected no
			  new region is defined, but the
			  point will be processed as if it
			  was a region.  Note that if the
			  global variable NOVICE is set to
			  NIL, TTY messages "VERIFY" and
			  "CHOOSE PT AGAIN" are suppressed.
		<sample> - specifies a single point.  No new
			       region is defined, but the point will
			       be processed as if it was a region.
		TTY: - LISP goes into a TTY break, and the user
			   should return a region designator.
		NIL - specifies the current region.
		In all cases, the region designator is mapped into a region
		number, either for an existing region, or for one created
		during the mapping.


	<bounding rectangle>	a rectangle defined implicitly by 
		the maximum and minimum values of I and J for the 
		samples of a region.



ISIS Function Descriptions

	All ISIS functions described below are LAMBDA functions,
unless otherwise specified.  In general, functions which access
properties of a region (such as its samples, boundary list, or hue)
first check to see if the property has been previously computed.
If it has been, the previous value is returned. Otherwise, the
value is computed and saved in a special hash array to be looked up
on the next access. This results in considerable time savings.

Starting ISIS

	ISIS exists as a SAVE file on directory <SUBSYS>. THerefore,
to run ISIS you need only type ISIS to TENEX. To operate on an image,
you must first load an ISIS fork with the function, ISISFORK,
and then load a picture into that fork using RDPIC. After running a 
while, you can save your work up to that point with the function,  
SAVESYS.

	ISISFORK [<forkname>]
		This function creates an inferior fork (after first 
		killing any existing ISIS fork), and loads the
		SAVE file specified by <forkname> into it.  It sets
		the global variable, ISISFORKNAME to <forkname>, and
		Will use this as a default value of <forkname>, if it 
		is not supplied in later invocations
		of the function. The file <ISIS>ISISF.SAV will be the
		most current default ISIS fork.

	RDPIC [<pic id>]
		RDPIC loads an image file into the ISIS fork.
		If <pic id> is a number, it references the picture 
		indexed by <pic id> on the index file, <VISION>INDX.DAT.
		If <pic id> is a filename, that file is loaded.

	SAVESYS [<filename>]
		saves anything you have added to ISIS on the
		TENEX file specified by <filename>.
		To restore the system to its saved state, type the
		filename to TENEX. It will automatically start ISIS
		and restore you to where you were. SAVESYS sets the
		globaL variable, SAVESYSNAME to the filename 
		specified. Thereafter, you need not supply the file
		name; it will use SAVESYSNAME as
		a default. When a SAVESYS file is restored, the ISIS
		fork in use when it was saved is restarted, and any
		picture previously loaded is reloaded.
  
	To save the region datastructures as a symbolic file, execute
the LISP form: MAKEFILE(DATASTRUC.ext), where ext is an extension
which you provide. They can be loaded into another incarnation of
ISIS with the LISP function, LOAD (i.e. LOAD(DATASTRUC.ext)).

Region Functions

	Regions are defined and accessed using the following functions.
ISIS is initialized with the first region defined as a 
boundary region of the whole picture with the alias, SCENE.


	NEWREGION [<region designator>; <type>]
		Defines a new region and makes it the current region.
		<type> = S or SMP for a sample region, B or BND for
		a boundary region, and NIL will cause the system to
		ask which type for region is being given.

	RESAMPLE [<region designator>; <sample density>]
		Resample the specified region.  Create a new region
		consisting of the sample points.
		<sample density> = If specified, causes RNDREGSZ to be
				   rebound to its value (see description
				   of RNDSMP below).

	SAMPLES [<region designator>]
		Returns the sample list for a region.  A sample list
		is created and saved if it does not already exist.

	BLIST [<region designator>]
		Returns the boundary list for a region.  A boundary
		list is created as a convex hull if it does not already
		exist.

	ALIAS [<alias>; <region number>]
		Defines an alias in terms of a region number.  If no
		region number is given then the region number associated
		with the alias is returned if the alias has been 
		previously defined.  If the alias has not been 
		previously defined and no region number is given the
		alias is associated with the current region.

	XREGION [<region number>]	deletes the specified region from
		the region data structure.

	CLRLDS [ ]	clears the region data structure, and reinitializes
		it to contain the SCENE as region 1.


Predicates

	LIMITP [<form>; <arg>; <min>; <max>]
		This predicate returns T if the (numeric) value of
		<form> applied to <arg> lies in the closed range of
		values specified by the minimum, <min>, and the
		maximum, <max>.

	WITHIN [I; J; <boundary list>]
		This program checks to see if the point (I . J) is 
		inside the region defined by <boundary list>.  It 
		returns NIL if the point is external to the region, 
		1 if internal, 2 if a boundary point, and 3 if a 
		vertex of the boundary.


Primitive Functions

	CVXHULL [<sample region>]
		This generates the convex hull of <sample region>.
		This is typically used as a default region boundary 
		for a sample region.

	RNDSMP [<boundary region>]
		This function selects random samples over <boundary 
		region>, and sets the region's samples to this collection. 
		The global variable, RNDREGSZ, sets the number of 
		points to be selected. If RNDREGSZ is an integer, 
		that number will be used as the number of points to 
		be selected; if it is a floating point number (which 
		must be between 0.0 and 1.0), the number is used as 
		a fraction of the IJ area of the region to be sampled. 
		For example, if RNDREGSZ has the value .25, RNDSMP will 
		randomly select one fourth of the samples of the 
		region and set the region's samples to be this 
		collection.  RNDREGMAX and RNDREGMIN are globals which 
		control the maximum and minimum number of samples 
		selected. RNDSMP will always select at least RNDREGMIN 
		samples, and at most RNDREGMAX samples.

REGIONS AND POINT PROPERTIES

     Region properties are determined by the following functions:

	BGHT [<region designator>] - average brightness of a region
	HEIGHT [<region designator>] - average height of a region
	HUE [<region designator>] - average hue of a region (defined below)
	ORIENT [<region designator>] - average orientation of a region 
		(defined below)
	RANGE [<region designator>] - average range of a region
	SAT [<region designator>] - average saturation of a region 
		(defined below)

     To each of the above functions the following suffixes may be
added to obtain different statistics:

	EXT - return the highest and lowest observed values
	SD - return the standard deviation of this feature
	S - return the value of the feature for a specific sample
	    point, bypassing the code to check what type of region
	    designator is given.  Use of the S functions will speed
	    up predicates.

     Other region property functions are:

	AREA [<region designator>] returns the total number of picture
				   points within a region.

	RGBR [<region number>] returns the average RGB coordinates
			       of picture points within a region.

	BRECT [<region designator>] returns the bounding rectangle
				    for the specified region.

     Point properties can be obtained by using the above functions,
or by using the "Q" functions which interrogate the low level data
structure.  Useful Q functions are listed below:

	SORQ [<sample>] returns the parameters of a plane fit to the
			3 X 3 matrix surrounding a point.

	XYZQ [<sample>] returns the real world coordinates of a 
			picture point in the form (X Y Z), measured
			in feet.

	SURFACEQ [<sample>] returns surface orientation and plane
			    intercepts for the 3 X 3 matrix surrounding
			    a point.

	IJQ [<real world point>] returns the picture coordinates
			         corresponding to a point in the
				 real world specified in the form
				 (X Y Z) measured in feet.


Display Functions

     As a default ISIS assumes that no display is assigned; to obtain
a display use the function:

	USEDISPLAY [<display  name>]
		<display name> =   NIL to use the default display 
					(currently RAMTEK)
				   ADAGE 
				   HP 
				   RAMTEK 
		The default display is reset to that specified
		by <display name>.

     To display the picture, use the function GRADIENT. This will
display a color picture if the RAMTEK is currently selected, or 
a gradient picture if the ADAGE or the HP is the current display.

	GRADIENT [<picture selector>; <scale>; <threshold>]
		<picture selector> (only for ADAGE or HP)
				   = BWPIC -- display picture taken 
					through neutral density filter.

				     REDPIC -- use picture taken through 
					red filter.

				     GREENPIC -- use picture taken through 
			   		green filter.

				     BLUEPIC -- use picture taken through 
			      		blue filter.

				     NIL -- use default picture 
					designated by the global variable 
					GRDFLTPIC (initially set to 
					REDPIC).

		<scale>		   = IDISPFS - full scale display
				     IDISPQS - quarter scale display

		<threshold>	   = gradient threshold, defaults to
				     the global IGRTHR which is initially
				     set to 7. This is only for the 
				     ADAGE or the HP.

	SHOW [<region designator>; BLINK]
		If BLINK is not NIL, blink the list displayed.

	SHOWCOLOR [<region designator>]
		Display region points in the color triangle.

	BOUNDARY [<region number>; BLINK]
		Display region boundary. If BLINK is not NIL,
		use blink mode.
		exist.


OTHER ISIS PROCEDURES

     Other useful ISIS functions are documented below:

	SMPRNT [<region number>; <form>]
		prints out the value of the form applied to each
		sample of the region.  e.g., SMPRNT (8 HUES) would
		print out the HUE of each sample in region 8.

	FILTER [<predicate>; <region designator>]
		A new current region is created, consisting of all
		samples in the old current region that make the 
		predicate true.  If the first argument is NIL then
		a predicate is built one clause at a time.  Clauses
		entered in this manner are combined conjunctively,
		and the variable X gets bound to each tested sample.

	GROW [<region designator>; <predicate>;
	      <window given as a list consisting of min x, max x,
	       min y, max y>; <growth increment>; <8-connectedness>]
		The opposite of filter, points are grown out from the
		boundary of the specified region.  Points within the
		window are considered at a spacing given by <growTH
		increment>.  Points are extended in a 4-connected
		sense if <8-connectedness> is NIL, and in an 8-connected
		sense otherwise.  Points are accepted if they make
		the predicate true.  After coarse growing is complete,
		the new boundary can be extended by growing in increments
		of 1 if the global variable GROW1 is non-nil.  The
		default for <growth-increment> is the global 
		GROW-DFLTDELTA which is initially set to 2.

Algorithms


WITHIN

	The procedure used by WITHIN to decide if a point is
internal or external to a region is to count the number of
boundary segments crossed by a line extending from the point to
another point outside the region.  An odd
number of crossings means the point is inside the region.
Special checks are be made to see if the point is a vertex
or lies on the boundary.  For a point, (I . J)  (Figure 1),
the external point selected is (I . 0).  The program
sequences through the boundary segments ignoring any segment
((I1 J1) (I2 J2)) unless I lies in the range, I1 to I2, and 
J is within the range J1 to J2, since these are
the only segments for which an intersection could exist.
For these segments, the intersection (IC . JC) is computed and
a crossing accurs if JC < J.  If JC = J then the point is on
the boundary.  In order to eliminate errors and to increase
efficiency, no divisions are performed by WITHIN.


CVXHULL

	In order to generate the convex hull of a set of
points, CVXHULL selects the extreme points in I and J as its
first guess at the boundary.  It then checks each remaining
point to see whether it is inside or outside the current
boundary.  Any point outside is inserted into the boundary.
At the end of this process, due to the unpredictable order
in which the points are selected, the boundary may have
concavities A final step cleans up this situation.

Algorithm for CVXHULL 

	1)	Select MAXIMA and MINIMA in I and J (Figure
		2), and generate initial boundary.

	2)	Check all remaining samples to determine
		whether inside or outside current boundary.  If
		outside, insert into boundary and continue.

	3)	Clean up concavities as described below.

In the example, assume points are checked in order shown in 
Figure 2. Figure 3 shows boundary after next five points have 
been checked. Figure 4 shows boundary after all points have been 
checked. Due to the order in which the 6th and 7th points were
checked, there is a slight concavity.  The last step clears
this up by moving around the boundary examining 4 points at
a time.  The second point is checked to see if it is inside
the triangular region defined by the first, third, and
fourth. If it is inside the traingle, it is deleted from the
boundary.  For example, in Figure 5, the point labeled 2 is
retained in the boundary, but in Figure 6, the point labeled
4 is within the traingle (3, 5, 6) and is, therefore,
removed from the boundary.

The true convex hull is shown in Figure 7. 


RNDSMP

RNDSMP works by computing an appropriately spaced grid over the
bounding rectangle of the region being sampled. The grid spacing
is determined bY the density of samples dictated by RNDREGSZ. 
A point is selected randomly from each grid cell (using the LISP 
random number generator, RAND), and checked to see if it is 
WITHIN the boundary region. If so, it is added to the 
list of samples being collected. The advantage of this approach 
is that the samples are uniformly distributed over the region, 
and the program need never check to see if the sample has 
already been generated. While the sampling is not completely 
random over the region, it is completely random within the grid cells.

HUE and SATURATION

------------------
to be typed
------------------


ORIENTATION

------------------
to be added
------------------